package hot100.logos51To60;

import java.util.Arrays;

/**
 * @author logos
 * date 2025/7/15 12:29
 * @version v1.0
 * @Package hot100.logos51To60
 */
public class logos54 {

    /**
     * 54. 实现Trie树
     * https://leetcode.cn/problems/implement-trie-prefix-tree/?envType=study-plan-v2&envId=top-100-liked
     */

    class Trie {

        private static final int MAX_N = 30700;

        private static final int MAX_M = 26;

        private static int[][] trie = new int[MAX_N][MAX_M];

        private static int[] pass = new int[MAX_N];

        private static int[] end = new int[MAX_N];

        private static int cnt;

        private static void clear() {
            for (int i = 0; i <= cnt; i++) {
                Arrays.fill(trie[i], 0);
                pass[i] = 0;
                end[i] = 0;
            }
        }

        public Trie() {
            clear();
            cnt = 1;
        }

        public void insert(String word) {
            int cur = 1;
            pass[cur]++;
            for (int i = 0, path; i < word.length(); i++) {
                path = word.charAt(i) - 'a';
                if (trie[cur][path] == 0) {
                    trie[cur][path] = ++cnt;
                }
                pass[cur]++;
                cur = trie[cur][path];
            }
            end[cur]++;
        }

        public boolean search(String word) {
            int cur = 1;
            for (int i = 0, path; i < word.length(); i++) {
                path = word.charAt(i) - 'a';
                if (trie[cur][path] == 0) {
                    return false;
                }
                cur = trie[cur][path];
            }
            return end[cur] > 0;
        }

        public boolean startsWith(String prefix) {
            int cur = 1;
            for (int i = 0, path; i < prefix.length(); i++) {
                path = prefix.charAt(i) - 'a';
                if (trie[cur][path] == 0) {
                    return false;
                }
                cur = trie[cur][path];
            }
            return true;
        }
    }
}
